package com.bo.day20231205;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 最大线段重合问题
 * 给定很多线段，每个线段都有两个数[start, end]，表示线段开始位置和结束位置，左右都是闭区间。
 * 规定:
 * 1)线段的开始和结束位置一定都是整数值
 * 2)线段重合区域的长度必须>=1
 * 返回线段最多重合区域中，包含了几条线段
 *
 * @Author: gpb
 * @Date: 2023/12/6 10:04
 * @Description:
 */
public class CoverMax {

    public static void main (String[] args) {

        Line l1 = new Line(4, 9);
        Line l2 = new Line(1, 4);
        Line l3 = new Line(7, 15);
        Line l4 = new Line(2, 4);
        Line l5 = new Line(4, 6);
        Line l6 = new Line(3, 7);

        // 底层堆结构，heap
        PriorityQueue<Line> heap = new PriorityQueue<>(new StartComparator());
        heap.add(l1);
        heap.add(l2);
        heap.add(l3);
        heap.add(l4);
        heap.add(l5);
        heap.add(l6);

        while (!heap.isEmpty()) {
            Line cur = heap.poll();
            System.out.println(cur.start + "," + cur.end);
        }

        System.out.println("test begin");
        int N = 100;
        int L = 0;
        int R = 200;
        int testTimes = 200000;
        for (int i = 0; i < testTimes; i++) {
            int[][] lines = generateLines(N, L, R);
            int ans1 = maxCover1(lines);
            int ans2 = maxCover2(lines);
            int ans3 = maxCover3(lines);
            if (ans1 != ans2 || ans1 != ans3) {
                System.out.println("Oops!");
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println(ans3);
            }
//            int ans2 = maxCover2(lines);
//            int ans3 = maxCover3(lines);
//            if (ans2 != ans3) {
//                System.out.println("Oops!");
//            }
        }
        System.out.println("test end");
    }


    /**
     * version_3 实现思路和version_2一样,只是这次不适用辅助类了
     *
     * @param m
     * @return
     */
    public static int maxCover3 (int[][] m) {
        // m是二维数组，可以认为m内部是一个一个的一维数组
        // 每一个一维数组就是一个对象，也就是线段
        // 如下的code，就是根据每一个线段的开始位置排序
        // 比如, m = { {5,7}, {1,4}, {2,6} } 跑完如下的code之后变成：{ {1,4}, {2,6}, {5,7} }
        Arrays.sort(m, (a, b) -> a[0] - b[0]);
        // 小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int max = 0;
        // 遍历开始位置的
        for (int[] ints : m) {
            //如果结束位置的数小于等于开始位置的需要弹出,因为此时的结束位置都小于等于开始的位置的数,肯定这两个线段是没有重合
            while (!heap.isEmpty() && heap.peek() <= ints[0]) {
                heap.poll();
            }
            heap.add(ints[1]);
            max = Math.max(max, heap.size());
        }
        return max;
    }

    /**
     * version_2 实现思路：
     * 1) 首先按照开始位置的数排好顺序(升序)
     * 2) 创建一个小根堆,来进行存储结束位置的数
     * 3) 遍历排好序开始位置的数,用开始的位置的数和小根堆结束位置的数,进行比较
     * 如果结束位置的数小于等于开始位置的需要弹出,因为此时的结束位置都小于等于开始的位置的数,肯定这两个线段是没有重合
     * 4) 把此时结束位置的数添加到小根堆里面
     * 5) 此时小根堆就是重合线段的数量
     * 6) 求出重合最多的次数,找到最多的小根堆即可
     *
     * @param arr
     * @return
     */
    public static int maxCover2 (int[][] arr) {
        Line[] lines = new Line[arr.length];
        for (int i = 0; i < arr.length; i++) {
            Line line = new Line(arr[i][0], arr[i][1]);
            lines[i] = line;
        }
        // 排序
        Arrays.sort(lines, (o1, o2) -> o1.start - o2.start);
        // 小根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue();
        int max = 0;
        for (Line line : lines) {
            //如果结束位置的数小于等于开始位置的需要弹出,因为此时的结束位置都小于等于开始的位置的数,肯定这两个线段是没有重合
            while (!priorityQueue.isEmpty() && priorityQueue.peek() <= line.start) {
                priorityQueue.poll();
            }
            priorityQueue.add(line.end);
            max = Math.max(max, priorityQueue.size());
        }
        return max;
    }


    /**
     * version_1实现思路：
     * 1) 找出最小的开始位置,和最大的结束位置
     * 2) 求出从最小的位置到最大的位置,每个0.5包含的线段次数,找出那个最大的即可
     * 比如：
     * arr[][]={{1,5},{3,4},{3,5}};
     * 最小的开始位置：1
     * 最大的结束位置：5
     * 1.5: 1个
     * 2.5: 1个
     * 3.5: 3个
     * 4.5: 2个
     * 开始位置：arr[0][0]
     * 结束位置：arr[0][1]
     *
     * @param arr
     * @return
     */
    public static int maxCover1 (int[][] arr) {
        // 开始 位置最小值
        int min = Integer.MAX_VALUE;
        // 结束 位置最大值
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            min = Math.min(min, arr[i][0]);
            max = Math.max(max, arr[i][1]);
        }
        int res = 0;
        // 求出从最小的位置到最大的位置,每个0.5包含的线段次数,找出那个最大的即可
        for (double i = min + 0.5; i < max; i += 1) {
            // 找出这个0.5出现的多个个线段
            int cur = 0;
            for (int i1 = 0; i1 < arr.length; i1++) {
                if (arr[i1][0] < i && arr[i1][1] > i) {
                    cur++;
                }
            }
            // 求出最大
            res = Math.max(res, cur);
        }
        return res;
    }

    public static class Line {
        public int start;
        public int end;

        public Line (int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    // for test
    public static int[][] generateLines (int N, int L, int R) {
        int size = (int) (Math.random() * N) + 1;
        int[][] ans = new int[size][2];
        for (int i = 0; i < size; i++) {
            int a = L + (int) (Math.random() * (R - L + 1));
            int b = L + (int) (Math.random() * (R - L + 1));
            if (a == b) {
                b = a + 1;
            }
            ans[i][0] = Math.min(a, b);
            ans[i][1] = Math.max(a, b);
        }
        return ans;
    }

    public static class StartComparator implements Comparator<Line> {

        @Override
        public int compare (Line o1, Line o2) {
            return o1.start - o2.start;
        }

    }
}
